import javax.swing.tree.TreeNode;
import java.awt.*;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2025-02-18
 * Time: 11:44
 */
public class test2 {
    /**
     * LeetCode 236   两个节点的最近公告节点
     */

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return null;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        getPath(root,p,stack1);
        getPath(root,q,stack2);

        // 看p与q之间的距离,让p和q处在同一层的节点上，无论是否重复
        int size1 = stack1.size();
        int size2 = stack2.size();

        if(size1>size2){
            int size = size1-size2;
            while(size!=0){
                stack1.pop();
                size--;
            }
        }
        if(size1<size2){
            int size = size2-size1;
            while(size!=0){
                stack2.pop();
                size--;
            }
        }
        // 此时已经处于同一层节点上，判断是否重合
        while(!stack1.isEmpty() && !stack2.isEmpty()){
            if(stack1.peek().equals(stack2.peek())){
                return stack1.pop();
            }else{
                stack1.pop();
                stack2.pop();
            }
        }
        // 找不到就返回空
        return null;

    }

    // 从上往下遍历，看p的位置在哪，依次将遍历的结果放入栈中
    public boolean getPath(TreeNode root, TreeNode node, Stack stack){
        if(root==null){
            return false;
        }
        stack.push(root);
        if(root==node){
            return true;
        }
        // 往左边找
        boolean flgLeft = getPath(root.left,node,stack);
        if(flgLeft){
            return true;
        }
        // 往右边找
        boolean flgRight = getPath(root.right,node,stack);
        if(flgRight){
            return true;
        }
        // 往左边或者右边没找到，那就把这个弹出去，去另外一边找
        stack.pop();
        return false;
    }


    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
}
